﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0133_IsValidBST : IAlgorithm
    {
        // 98. 验证二叉搜索树

        // 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

        // 有效 二叉搜索树定义如下：
        //  节点的左子树只包含 小于 当前节点的数。
        //  节点的右子树只包含 大于 当前节点的数。
        //  所有左子树和右子树自身必须也是二叉搜索树。

        // 提示：
        //  树中节点数目范围在[1, 10^4] 内
        //  -2^31 <= Node.val <= 2^31 - 1

        public void Test()
        {
            // 算法参数定义
            var root = new TreeNode(int.MinValue);
            // 算法执行与打印
            Console.WriteLine(IsValidBST(root));
        }

        // 算法
        public bool IsValidBST(TreeNode root)
        {
            var stack = new Stack<TreeNode>();
            var inorder = long.MinValue;
            while (stack.Count > 0 || root != null)
            {
                while (root != null)
                {
                    stack.Push(root);
                    root = root.left;
                }
                root = stack.Pop();
                if (root.val <= inorder)
                    return false;
                inorder = root.val;
                root = root.right;
            }
            return true;
        }
    }
}
